// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
	"math"
)

func ArraySort(array []int) []int {
	return radixSort(array)
}

func radixSort(array []int) []int {
	// 最长的数字有多少位
	maxDigitCount := digitCount(maxNumber(array))
	// 根据第k位的数字放入桶中
	for k := 0; k < maxDigitCount; k++ {
		digitBuckets := make([][]int, 10)
		for i := 0; i < len(array); i++ {
			digitAtKposition := getDigit(array[i], k)
			digitBuckets[digitAtKposition] = append(digitBuckets[digitAtKposition], array[i])
		}
		// 从桶中获取
		array = getFromBuckets(digitBuckets)
	}
	// 对负数进行排序，我们可以将一个符号视为另一个桶
	signBuckets := make([][]int, 2)
	for i := 0; i < len(array); i++ {
		if array[i] < 0 {
			signBuckets[0] = append(signBuckets[0], array[i])
		} else {
			signBuckets[1] = append(signBuckets[1], array[i])
		}
	}
	// 反转负数数组
	reverse(signBuckets[0])
	array = getFromBuckets(signBuckets)
	return array
}
func getFromBuckets(digitBuckets [][]int) []int {
	array := make([]int, 0)
	for i := range digitBuckets {
		array = append(array, digitBuckets[i]...)
	}
	return array
}
func getDigit(num, place int) int {
	return int(math.Floor(float64(abs(num))/math.Pow(10, float64(place)))) % 10
}
func digitCount(num int) int {
	if num == 0 {
		return 1
	}
	return int(math.Floor(math.Log10(float64(abs(num))))) + 1
}
func reverse(array []int) {
	length := len(array)
	for i := 0; i < length/2; i++ {
		array[i], array[length-i-1] = array[length-i-1], array[i]
	}
}
func maxNumber(array []int) int {
	result := math.MinInt64
	for _, num := range array {
		// !number can be negative
		if result < abs(num) {
			result = abs(num)
		}
	}
	return result
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func main() {
	array := []int{18, 6, 8, 1}
	res := ArraySort(array)
	fmt.Println(res)
}

//$ go run interview6-14.go
//[1 6 8 18]
